package sort;

public class merge {
   private static Comparable[] tem;

    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        tem =new Comparable[a.length];
        sort(a, lo, hi);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int left = lo;
        int right = mid + 1;
        int assist = lo;
        while (left <= mid && right <= hi) {
            if (grate(a[left], a[right])) {
                tem[assist++] = a[right++];
            } else {
                tem[assist++] = a[left++];
            }
        }
        //将没有比较的数字，直接加入数组
        while (left <= mid) {
            tem[assist++] = a[left++];
        }
        //将没有比较的数字，直接加入数组
        while (right <= hi){
            tem[assist++] = a[right++];
        }
        //将新数组中的内容转给原数组
        for (int i = 0 ; i<= hi; i++){
            a[i] = tem[i];
        }
    }

    //判断两个数值的大小
    private static Boolean grate(Comparable x, Comparable y) {
        return x.compareTo(y) > 0;
    }

    //交换两个元素的位置
    private static void exch(Comparable[] a, int i, int j) {
        Comparable tem = a[i];
        a[i] = a[j];
        a[j] = tem;
    }
}
